package com.lfc.math;

import java.util.*;

public class ZeroOnePackTest {
    public static void main(String[] args) {
        int[] value = {3, 4, 5, 8};
        int[] weght = {2, 3, 4, 5};
        int V = 8;
        int N = 4;
        // 初步版本
//        System.out.println(ZeroOnePack(V, N, weght, value));
//        System.out.println(ZeroOnePack1(V, N, weght, value));
        // 优化版本
//        System.out.println(completePack(V, N, weght, value));
//        String s = "(a)(a)(a)aaa";
        List<List<String>> ast = new ArrayList<>();
        List<String> art1 = new ArrayList<>();
        art1.add("a");
        art1.add("yes");
        ast.add(art1);
//        System.out.println(evaluate(s, ast));
//        String s = "030";
//        System.out.println(digitCount(s));
        String s = "abcba";
        String target = "abc";
        System.out.println(rearrangeCharacters(s, target));
    }

    /**
     * 01背包问题的简单解法
     *
     * @param V   背包容量
     * @param N   背包种类
     * @param wgt 物品的重量
     * @param val 物品的价值
     * @return 最大价值
     */
    public static int ZeroOnePack(int V, int N, int[] wgt, int[] val) {
        // 使用动态规划数组
        int[][] dp = new int[N + 1][V + 1];
        //为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= V; j++) {
                //如果第i件物品的重量大于背包容量j,则不装入背包
                //由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]
                if (wgt[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wgt[i - 1]] + val[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[N][V];
    }

    public static int ZeroOnePack1(int V, int N, int[] wgt, int[] val) {
        int[] dp = new int[V + 1];
        for (int i = 0; i < N; i++) {
            for (int j = V; j >= wgt[i]; j--) {
                dp[j] = Math.max(dp[j - wgt[i]] + val[i], dp[j]);
            }
        }
        return dp[V];
    }

    public static int completePack(int V, int N, int[] wgt, int[] val) {
        int[] dp = new int[V + 1];
        for (int i = 0; i < N; i++) {
            for (int j = wgt[i]; j <= V; j++) {
                dp[j] = Math.max(dp[j], dp[j - wgt[i]] + val[i]);
            }
        }
        return dp[V];
    }

    public static boolean digitCount(String num) {
        int[] arr = new int[10];
        for (char c : num.toCharArray()) {
            arr[c - '0']++;
        }
        for (int i = 0; i < num.length(); i++) {
            if (num.charAt(i) - '0' != arr[i]) {
                return false;
            }
        }
        return true;
    }

    public static String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        for (List<String> v : knowledge) map.put(v.get(0), v.get(1));
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                int j = i;
                while (s.charAt(++j) != ')') ;
                String key = s.substring(i + 1, j);
                sb.append(map.getOrDefault(key, "?"));
                i = j;
            } else sb.append(s.charAt(i));
        }
        return sb.toString();
    }

    public static int rearrangeCharacters(String s, String target) {
        int res = 0;
        int[] map = new int[26];
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i) - 'a']++;
        }
        while (true) {
            for (int i = 0; i < target.length(); i++) {
                map[target.charAt(i) - 'a']--;
                if (map[target.charAt(i) - 'a'] < 0) return res;
            }
            res++;
        }
    }

    public static boolean checkXMatrix(int[][] grid) {
        int n = grid.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || i + j + 1 == n) {
                    if (grid[i][j] == 0) return false;
                } else {
                    if (grid[i][j] != 0) return false;
                }
            }
        }
        return true;
    }

}
